/*
 * Diseno de Algoritmos 2
 * Abril Julio 2011
 * David Subero
 * Daniel Bruzual
 * Job Shop resuelto a traves de varias metaheuristicas
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <unistd.h>

#include "jobshop.h"
#include "Lista.h"
#include <time.h>

//numero de trabajos
int nro_t;

//numero de maquinas
int nro_m; 

//numero de operaciones totales 
int nro_op;

/* arreglo que contiene todas las operaciones
 * ordenadas por trabajo, y por precedencia
 * dentro de ese trabajo.
*/
operacion *operaciones;

/* Mejor solucion encontrada hasta el momento representada como una
 * matriz que contiene por cada maquina, las operaciones en el 
 * orden que se realizan en ella
 */
operacion ***mejor_solucion;

//Costo de la mejor solucion hasta el momento
int costo_mejor;

//Lista taboo utilizando una matriz. Guarda los movimientos prohibidos
int **taboo;

//operaciones iniciales de cada maquina
operacion **inicio; 

//operaciones finales de cada maquina
operacion **fin;

/* Lee el archivo de una instancia e inicializa todas las estructuras
 * Parametros:
 *		archivo: nombre del archivo de la instancia
 * Valor de retorno:
 *		1 si el archivo no existe o si el formato del archivo no es valido
 *		-1 si no hay suficiente memoria disponible
 *		0 en otro caso
 */
int leer_instancia (char *archivo) {
  int i, j, maquina, costo;
  operacion *predecesor;
  FILE *fp;
  if ((fp = fopen(archivo, "r")) == NULL) {
    printf("ERROR: no se encontro el archivo \"%s\"\n",archivo);
    return 1;
  }

  if(!fscanf(fp, "%d %d\n", &nro_t, &nro_m)) {
    printf("ERROR: formato invalido\n");
    return 1;
  }
	
  //todas los trabajos tienen una operacion por maquina
  nro_op = nro_t * nro_m; 

  operaciones = (operacion *) calloc(nro_op,sizeof(operacion));
  if (operaciones == NULL) return -1;
  mejor_solucion = (operacion ***) calloc(nro_m,sizeof(operacion **));
  if (mejor_solucion == NULL) return -1;
  inicio = (operacion **) calloc(nro_m,sizeof(operacion *));
  if (inicio == NULL) return -1;
  fin = (operacion **) calloc(nro_m, sizeof(operacion *));
  if (fin == NULL) return -1;
  taboo = (int **) calloc(nro_op,sizeof(int *));
  if (taboo == NULL) return -1;
  
  for (i=0; i<nro_op; i++) {
  	taboo[i] = (int *) calloc(nro_op,sizeof(int));
  	if (taboo[i] == NULL) return -1;
  }
  
  for (i=0; i<nro_m; i++) {
    mejor_solucion[i] = (operacion **) calloc(nro_t,sizeof(operacion *));
    if (mejor_solucion[i] == NULL) return -1;
  }
	
  for (i=0; i<nro_t; i++) {
    predecesor = NULL;
    for (j=0; j<nro_m; j++) {
      if(!fscanf(fp, "%d %d\n", &maquina, &costo)) {
	printf("ERROR: formato invalido\n");
	return 1;
      }
      operaciones[i*nro_m + j].id = i*nro_m + j;
      operaciones[i*nro_m + j].costo = costo;
      operaciones[i*nro_m + j].maquina = maquina;
      operaciones[i*nro_m + j].pj = predecesor;
      operaciones[i*nro_m + j].pm = operaciones[i*nro_m + j].sm = NULL;
      if (j < nro_m - 1) {
	operaciones[i*nro_m + j].sj = operaciones + i*nro_m + j + 1;
      } else {
	operaciones[i*nro_m + j].sj = NULL;
      }
      
      predecesor = operaciones + i*nro_m + j;
    }
  }
  fclose(fp);
  return 0;
}

/* Elimina un elemento de un arreglo de enteros
 * Parametros:
 *		arr: el arreglo donde se va a eliminar el elemento
 *		tam: longitud del arreglo arr
 *		elem: elemento del arreglo que se quiere eliminar
 */
void quitar(int* arr, int tam, int elem){
  int i;
  for(i = 0; i<tam; i++){
    if(arr[i] == elem){
      arr[i] = arr[tam-1];
      return;
    }
  }
}

/* Heuristica que selecciona la proxima operacion a planificar
 * Parametros:
 *		arr: arreglo de operaciones candidatas a ser planificadas
 *		tam: longitud del arreglo arr
 * Valor de retorno:
 *		operacion seleccionada para ser planificada
 */
int mejor_operacion(int* arr, int tam){
  int estimado[tam], i, count, j;
  int max=-1, max_val;

  for(i=0; i<tam; i++){
    estimado[i] = 0;
    for(j=arr[i]; j<(((arr[i]/nro_m)+1)*nro_m)-1; j++) {
      estimado[i] += operaciones[j].costo;
    }
  }

  max = 0;
  max_val = estimado[0];
  for(i=1; i<tam; i++){
    if(estimado[i] > max_val){
      max_val = estimado[i];
      max = i;
    }
  }

  return arr[max];
}

/* Selecciona aleatoriamente la proxima operacion a planificar
 * Parametros:
 *		arr: arreglo de operaciones candidatas a ser planificadas
 *		tam: longitud del arreglo arr
 * Valor de retorno:
 *		operacion seleccionada para ser planificada
 */
int operacion_aleatoria(int* arr, int tam){
  return arr[rand() % tam];
}

/* Algoritmo list-schedule que genera una solucion inicial de manera greedy
 * Parametros:
 *		prim_cad_maq: arreglo de operaciones iniciales de cada maquina
 *		ult_cad_maq: arreglo de operaciones finales de cada maquina
 *      modalidad: entero que indica como es la solucion inicial.
 *                 Si el parametro es 0, la solucion es deterministica, en
 *                 otro caso, la solucion es aleatoria
 */
void solucion_naive(operacion * prim_cad_maq[], operacion * ult_cad_maq[], int modalidad){
  int i, t, tam_L, maq_t;
  int disponible[nro_m], L[nro_op];
  int (*operacion_a_asignar)(int *,int);
  
  if (modalidad == 0) {
    operacion_a_asignar = mejor_operacion;
  } else {
    operacion_a_asignar = operacion_aleatoria;
  }

  for(i=0; i<nro_t; i++){
    L[i] = nro_m*i;
  }
  tam_L = nro_t;
  for(i=0; i<nro_m; i++){
    disponible[i] = 0;
    ult_cad_maq[i] = 0;
    prim_cad_maq[i] = 0;
  }
   
  while(tam_L > 0){
    t = operacion_a_asignar(L, tam_L);
    maq_t = operaciones[t].maquina;

    if (disponible[maq_t] != 0) {
      operaciones[t].pm = ult_cad_maq[maq_t];
      ult_cad_maq[maq_t]->sm = operaciones + t;
    } else {
      prim_cad_maq[maq_t] = operaciones + t;
      //new
      operaciones[t].pm = 0;
    }

    ult_cad_maq[maq_t] = operaciones + t;

    disponible[maq_t]++;
    quitar(L, tam_L, t);
    tam_L--;
    if((t+1) % nro_m != 0){
      L[tam_L] = t+1;
      tam_L++;
    }
  }
}

/* Imprime una solucion
 * Parametros:
 *		solucion: matriz que representa una solucion y contiene por cada maquina,
 *                las operaciones en el orden que se realizan en ella
 *		comienzo: arreglo que contiene los tiempos de comienzo de cada operacion
 */
void imprimir_solucion (operacion *** solucion, int comienzo[]) {
  int i, j;
  operacion *op;
  printf("Operaciones ordenadas en cada maquina segun se realizan.\n");
  printf("Solucion:\t(job, operation)\n");

  for (i=0; i<nro_m; i++) {
    printf("Maquina %d: ", i);
    for (j=0; j<nro_t; j++) {
        op = solucion[i][j];
        printf("(%d,%d)  ",op->id / nro_m, op->id % nro_m);
    }
    printf("\n");
  }
}

/* Calcula recursivamente el tiempo de comienzo mas temprano de la operacion op
 * Parametros:
 *		operaciones_est: arreglo de tiempos de comienzo mas temprano
 *						 de cada operacion
 *		op: operacion de la cual se esta calculando el tiempo
 * Valor de retorno:
 *		tiempo de comienzo mas temprano de la operacion op
 */
int calcular_r (int operaciones_est[], operacion *op) {
  int est, eft_pj = -1, eft_pm = -1;
  if (!operaciones_est[op->id]) {
    if (op->pm) {
      eft_pm = calcular_r(operaciones_est,op->pm) + op->pm->costo;
    }
    if (op->pj) {
      eft_pj = calcular_r(operaciones_est,op->pj) + op->pj->costo;
    }

    est = operaciones_est[op->id] = MAX(eft_pj, eft_pm);

    if(est == -1){
      est = operaciones_est[op->id] = 0;
    }
  } else {
    est = operaciones_est[op->id];
  }
  return est;
}

/* Calcula recursivamente el tiempo desde que termina la operacion op
 * hasta que finalizan todos los trabajos
 * Parametros:
 *		colas: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 *		op: operacion de la cual se esta calculando el tiempo
 * Valor de retorno:
 *		tiempo desde que termina la operacion op hasta que finalizan
 *		todos los trabajos
 */
int calcular_t(int colas[], operacion *op ){
  int est, est_sm = -1, est_sj = -1;
  if(!colas[op->id]){
    if(op->sm){
      est_sm = calcular_t(colas, op->sm) + op->sm->costo;
    }
    if(op->sj){
      est_sj = calcular_t(colas, op->sj) + op->sj->costo;
    }

    est = colas[op->id] = MAX(est_sm, est_sj);

    if(est == -1){
      est = colas[op->id] = 0;
    }
  } else {
    est = colas[op->id];
  }
  return est;
}

/* Calcula el costo de una solucion, el tiempo de comienzo mas temprano
 * de cada operacion y el tiempo desde que termina cada operacion hasta
 * que finalizan todos los trabajos
 * Parametros:
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		ultimos: arreglo de operaciones finales de cada maquina
 *		operaciones_est: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		colas: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		tiempo desde que inicia la primera operacion hasta que finaliza la ultima operacion
 */
int costo_solucion (operacion * primeros[], operacion * ultimos[], int* operaciones_est, int* colas) {
  int i, est, max;

  for (i=0; i<nro_op; i++) {
    operaciones_est[i] = 0;
    colas[i] = 0;
  }
  est = calcular_r(operaciones_est,ultimos[0]);
  max = ultimos[0]->id;
  for (i=1; i<nro_m; i++) {
    est = calcular_r(operaciones_est,ultimos[i]) +  ultimos[i]->costo;
    if (est > operaciones_est[max] + operaciones[max].costo) {
      max = ultimos[i]->id;
    }
  }	

  for(i=0; i<nro_m; i++){
    calcular_t(colas, primeros[i]);
  }

  return operaciones_est[max] + operaciones[max].costo;
}

/* Calcula los nodos que estan en el camino critico y
 * guarda el id de cada uno en un arreglo llamado nodos
 * Parametros:
 *		nodos: arreglo que contiene los id de las operaciones que se encuentran
 *			   en el camino critico
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		cantidad de operaciones del camino critico
 */
int camino_critico(int ** nodos, operacion ** primeros, int costo_sol, int r_sol[], int t_sol[]){
  int i, id, tama;
  operacion* op,* sm,* sj, *sig;
  Lista camino;
  inicializa(&camino);
  
  //buscar la primera operacion de alguna maquina
  //que sea parte de un camino critico
  for(i=0; i<nro_m; i++){
    op = primeros[i];
    if(op->costo + t_sol[op->id] == costo_sol){
      //es el primer nodo de un camino critico
      push(op->id, &camino);
      sig = op;
      break;
    }
  }

 //recorrer el grafo buscando UN camino critico
 while(sig != NULL){
   sm = sig->sm;
   sj = sig->sj;
   if(sm != NULL && r_sol[sm->id] + sm->costo + t_sol[sm->id] == costo_sol
      && r_sol[sm->id] - sig->costo == r_sol[sig->id]){
     //el sucesor en la maquina forma parte del camino critico
     push(sm->id, &camino);
     sig = sm;
   } else if(sj != NULL){
     //si el sucesor en la maquina no esta en el camino critico
     //entonces el sucesor en trabajo si lo esta
     push(sj->id, &camino);
     sig = sj;
   } else {
     sig = NULL;
   }
 }
  
  //Copiar el resultado a un arreglo
  tama = tam(&camino);
  *nodos = (int *) calloc(tama, sizeof(int));

  for(i=0; i<tama; i++){
    (*nodos)[i] = desencolar(&camino);
  }
  return tama;
}

/* Calcula una cota inferior para el costo resultante de cambiar
 * el orden de las num_nodos operaciones que estan en el orden
 * actual[] en alguna maquina para que queden en el orden de 
 * acuerdo a nodos[].
 * Parametros:
 *		num_nodos: cantidad de operaciones que van a ser intercambiadas
 *		actual: arreglo que representa el orden actual en una maquina
 *				de las num_nodos operaciones
 *		nodos: arreglo que representa el orden despues del intercambio
 *			   en una maquina de las num_nodos operaciones
 *		r: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t: arreglo de tiempos desde que termina cada operacion hasta que
 *		   finalizan todos los trabajos
 * Valor de retorno:
 *		cota inferior del intercambio entre operaciones
 */
int lpath(int num_nodos, operacion* actual[], operacion* nodos[], int r[], int t[]){
  int r_est[num_nodos], t_est[num_nodos];
  int i, j;
  operacion * a, * b;
  i=0;
  a = nodos[i];
  if(a->pj == NULL && actual[i]->pm != NULL){
    r_est[i] = r[actual[i]->pm->id] + actual[i]->pm->costo;
  } else if(a->pj != NULL && actual[i]->pm == NULL){
    r_est[i] = r[a->pj->id] + a->pj->costo;
  } else if(a->pj != NULL && actual[i]->pm != NULL){
    r_est[i] = MAX(r[a->pj->id] + a->pj->costo, 
		   r[actual[i]->pm->id] + actual[i]->pm->costo);
  } else {
    r_est[i] = 0; //nuevo
  } 
  
  for(i=1; i<num_nodos; i++){ 
    b = nodos[i];
    if(b->pj != NULL){
      r_est[i] = MAX(r[b->pj->id] + b->pj->costo,
		     r_est[i-1]+a->costo);
    } else {
      r_est[i] = r_est[i-1]+a->costo;
    }
    a = b;
  }

  i = num_nodos - 1;
  b = nodos[i];
  if(b->sj != NULL && actual[i]->sm != NULL){
    t_est[i] = MAX(t[b->sj->id] + b->sj->costo,
		   t[actual[i]->sm->id] + actual[i]->sm->costo);
  } else if(b->sj != NULL && actual[i]->sm == NULL){
    t_est[i] = t[b->sj->id] + b->sj->costo;
  } else if(b->sj == NULL && actual[i]->sm != NULL){
    t_est[i] = t[actual[i]->sm->id] + actual[i]->sm->costo;
  } else {
    t_est[i] = 0;
  }

  for(i=num_nodos-2; i>=0; i--){
    a = nodos[i];
    if(a->sj != NULL){
      t_est[i] = MAX(t[a->sj->id] + a->sj->costo,
		     t_est[i+1]+a->costo);
    } else {
      t_est[i] = t_est[i+1]+a->costo;
    }
    b = a;
  }

  int max_cam = -1;
  for(i=0; i<num_nodos; i++){
    max_cam = MAX(r_est[i] + nodos[i]->costo  + t_est[i], max_cam);
  }
  return max_cam;
}

/* Para dos operaciones u,v consecutivas en la misma maquina, que ademas
 * son parte de un camino critico, halla cual es el mejor movimiento
 * que se puede hacer cambiandolos de orden, entre si y con sus sucesores
 * o predecesores
 * Parametros:
 *		u: operacion predecesora de la operacion v en una maquina x
 *		v: operacion sucesora de la operacion u en una maquina x
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el mejor movimiento de u y v
 *		mejor: arreglo que representa el orden de las operaciones
 *			   despues de ejecutar el mejor movimiento
 * Valor de retorno:
 *		cantidad de operaciones involucradas en el mejor movimiento
 */
int estim(operacion * u, operacion * v, operacion * actual[], operacion * mejor[],
	  int r[], int t[], int *mejor_cota){
  operacion *nodos[3], *actual_aux[3];
  int e, tam =2;
  actual_aux[0] = u;
  actual_aux[1] = v;
  nodos[0] = v;
  nodos[1] = u;
  *mejor_cota = lpath(2, actual_aux, nodos, r, t);
  memcpy(mejor, nodos, 2*sizeof(operacion *));
  memcpy(actual, actual_aux, 2*sizeof(operacion *));

  if(u->pm != NULL){
    actual_aux[0] = u->pm;
    actual_aux[1] = u;
    actual_aux[2] = v;
    nodos[0] = v;
    nodos[1] = u->pm;
    nodos[2] = u;
    if((e = lpath(3, actual_aux, nodos, r, t)) < *mejor_cota){
      *mejor_cota = e;
      memcpy(mejor, nodos, 3*sizeof(operacion *));
      memcpy(actual, actual_aux, 3*sizeof(operacion *));
      tam = 3;
    }
    nodos[0] = v;
    nodos[1] = u;
    nodos[2] = u->pm;
    if((e = lpath(3, actual_aux, nodos, r, t)) < *mejor_cota){
      *mejor_cota = e;
      memcpy(mejor, nodos, 3*sizeof(operacion *));
      memcpy(actual, actual_aux, 3*sizeof(operacion *));
      tam = 3;
    }
  }
  if(v->sm != NULL){
    actual_aux[0] = u;
    actual_aux[1] = v;
    actual_aux[2] = v->sm;
    nodos[0] = v;
    nodos[1] = v->sm;
    nodos[2] = u;
    if((e = lpath(3, actual_aux, nodos, r, t)) < *mejor_cota){
      *mejor_cota = e;
      memcpy(mejor, nodos, 3*sizeof(operacion *));
      memcpy(actual, actual_aux, 3*sizeof(operacion *));
      tam = 3;
    }
    nodos[0] = v->sm;
    nodos[1] = v;
    nodos[2] = u;
    if((e = lpath(3, actual_aux, nodos, r, t)) < *mejor_cota){
      *mejor_cota = e;
      memcpy(mejor, nodos, 3*sizeof(operacion *));
      memcpy(actual, actual_aux, 3*sizeof(operacion *));
      tam = 3;
    }
    
  }
  return tam;
}

/* Calcula el movimiento que se debe realizar para obtener el mejor vecino
 * segun la vecindad NA
 * Parametros:
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el mejor movimiento
 *		mejor: arreglo que representa el orden de las operaciones
 *			   despues de ejecutar el mejor movimiento
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		ultimos: arreglo de operaciones finales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		-1 en caso de no encontrar algun vecino que no esta prohibido
 *		en otro caso, cantidad de operaciones involucradas en el mejor movimiento
 */
int mejor_movimiento_na (operacion *actual[], operacion *mejor[], operacion ** primeros, operacion ** ultimos, int costo_sol, int r_sol[], int t_sol[]) {
  int i, *cam_crit, tam_cam_crit, u, v;
  int mejor_cota, mejor_cota_aux, tam_movimiento, tam_movimiento_aux;
  operacion *actual_aux[3], *mejor_aux[3];

  int found = 0;
  tam_cam_crit = camino_critico(&cam_crit, primeros, costo_sol, r_sol, t_sol);
	
  //busco un primer movimiento
  for (i=0; i<tam_cam_crit-1; i++) {
      if (operaciones[cam_crit[i]].maquina == operaciones[cam_crit[i+1]].maquina) {
	
	  tam_movimiento = estim(operaciones + cam_crit[i],
				 operaciones + cam_crit[i+1],
				 actual,mejor,r_sol,t_sol,&mejor_cota);

	  if (!taboo[cam_crit[i]][cam_crit[i+1]]) {
	    u = cam_crit[i];
	    v = cam_crit[i+1];
	    i++;
	    found = 1;
	    break;
	  } else { //aspiracion
	  }
      }
  }
  //busco el mejor movimiento
  for (; i<tam_cam_crit-1; i++) {
    if (!taboo[cam_crit[i]][cam_crit[i+1]]) {
      if (operaciones[cam_crit[i]].maquina == operaciones[cam_crit[i+1]].maquina) {

	tam_movimiento_aux = estim(operaciones + cam_crit[i],
				   operaciones + cam_crit[i+1],
				   actual_aux,mejor_aux,r_sol,t_sol,&mejor_cota_aux);
	if (mejor_cota_aux < mejor_cota) {
	  mejor_cota = mejor_cota_aux;
	  tam_movimiento = tam_movimiento_aux;
	  memcpy(actual, actual_aux, tam_movimiento*sizeof(operacion *));
	  memcpy(mejor, mejor_aux, tam_movimiento*sizeof(operacion *));
	  u = cam_crit[i];
	  v = cam_crit[i+1];
	}
	found = 1;
      }
    }
  }
  if(!found) return -1;
 
  free(cam_crit);

  return tam_movimiento;
}

/* Ejecuta el movimiento de las operaciones que se encuentran en el orden
 * representado por el arreglo actual para que queden en el orden representado
 * por el arreglo movimiento
 * Parametros:
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el movimiento
 *		movimiento: arreglo que representa el orden de las operaciones
 *					despues de ejecutar el movimiento
 *		tam_movimiento: cantidad de operaciones involucradas en el movimiento
 *		inicial: arreglo de operaciones iniciales de cada maquina
 *		final: arreglo de operaciones finales de cada maquina
 */
void hacer_movimiento (operacion *actual[], operacion *movimiento[], int tam_movimiento, operacion * inicial[], operacion * final[]) {
  int i, j;
  
  movimiento[0]->pm = actual[0]->pm;
  if (actual[0]->pm) {
    actual[0]->pm->sm = movimiento[0];
  } else {
    inicial[movimiento[0]->maquina] = movimiento[0];
  }
	
  movimiento[tam_movimiento-1]->sm = actual[tam_movimiento-1]->sm;
  if (actual[tam_movimiento-1]->sm) {
    actual[tam_movimiento-1]->sm->pm = movimiento[tam_movimiento-1];
  } else {
    final[movimiento[tam_movimiento-1]->maquina] = movimiento[tam_movimiento-1];
  }

  for (i=0; i<tam_movimiento-1; i++) {
    movimiento[i]->sm = movimiento[i+1];
    movimiento[i+1]->pm = movimiento[i];
  }
}

/* Calcula el movimiento que se debe realizar para obtener el mejor vecino
 * segun la vecindad N1
 * Parametros:
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el mejor movimiento
 *		mejor: arreglo que representa el orden de las operaciones
 *			   despues de ejecutar el mejor movimiento
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		ultimos: arreglo de operaciones finales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		-1 en caso de no encontrar algun vecino que no esta prohibido
 *		en otro caso, cantidad de operaciones involucradas en el mejor movimiento
 */
int mejor_movimiento_n1 (operacion *actual[], operacion *mejor[], operacion ** primeros, operacion ** ultimos, int costo_sol, int r_sol[], int t_sol[]) {
  int i, *cam_crit, tam_cam_crit, u, v;
  int mejor_cota, mejor_cota_aux, tam_movimiento, tam_movimiento_aux;
  operacion *actual_aux[3], *mejor_aux[3];

  int found = 0;
  tam_cam_crit = camino_critico(&cam_crit, primeros, costo_sol, r_sol, t_sol);
	
  //busco un primer movimiento
    for (i=0; i<tam_cam_crit-1; i++) {
        if (operaciones[cam_crit[i]].maquina == operaciones[cam_crit[i+1]].maquina) {
            if (!taboo[cam_crit[i]][cam_crit[i+1]]) {
                actual[0] = operaciones + cam_crit[i];
				actual[1] = operaciones + cam_crit[i+1];
				mejor[0] = operaciones + cam_crit[i+1];
				mejor[1] = operaciones + cam_crit[i];
				hacer_movimiento(actual,mejor,2,primeros,ultimos);
				mejor_cota = costo_solucion(primeros, ultimos, r_sol, t_sol);
				hacer_movimiento(mejor,actual,2,primeros,ultimos);
				u = cam_crit[i];
				v = cam_crit[i+1];
				i++;
				found = 1;
				break;
            } else { //aspiracion
            }
        }
    }
    //busco el mejor movimiento
    for (; i<tam_cam_crit-1; i++) {
        if (!taboo[cam_crit[i]][cam_crit[i+1]]) {
            if (operaciones[cam_crit[i]].maquina == operaciones[cam_crit[i+1]].maquina) {
                actual_aux[0] = operaciones + cam_crit[i];
				actual_aux[1] = operaciones + cam_crit[i+1];
				mejor_aux[0] = operaciones + cam_crit[i+1];
				mejor_aux[1] = operaciones + cam_crit[i];
				hacer_movimiento(actual_aux,mejor_aux,2,primeros,ultimos);
				mejor_cota_aux = costo_solucion(primeros, ultimos, r_sol, t_sol);
				hacer_movimiento(mejor_aux,actual_aux,2,primeros,ultimos);
                if (mejor_cota_aux < mejor_cota) {
                    mejor_cota = mejor_cota_aux;
                    memcpy(actual, actual_aux, 2*sizeof(operacion *));
                    memcpy(mejor, mejor_aux, 2*sizeof(operacion *));
                    u = cam_crit[i];
                    v = cam_crit[i+1];
                }
            }
        }
    }
  if(!found) return -1;
 
  free(cam_crit);

  return 2;
}

/* Metaheuristica que mejora una solucion inicial haciendo busqueda local
 * y utilizando una estructura de memoria que describen las soluciones
 * visitadas
 * Parametros:
 *		mejor_vecindad: funcion que devuelve el mejor movimiento a realizar
 *						de acuerdo a una vecindad en particular
 *      modalidad: entero que indica como es la solucion inicial.
 *                 Si el parametro es 0, la solucion es deterministica, en
 *                 otro caso, la solucion es aleatoria
 *		taboo_size: longitud de la lista taboo
 */
void tabu_search (int (*mejor_vecindad)(), int modalidad, int taboo_size) {
  int i, j, k, r_sol[nro_op], t_sol[nro_op], *cam_crit, tam_cam_crit;
  int costo_actual, tam_movimiento, nro_iteraciones = 0;
  operacion* primeros[nro_m], *ultimos[nro_m], *actual[3], *movimiento[3];
  

    solucion_naive(primeros, ultimos, modalidad);


  costo_mejor = costo_actual = costo_solucion(primeros, ultimos, r_sol, t_sol);



  for (i=0; i<1000; i++) {//criterio de parada

    tam_movimiento = mejor_vecindad(actual, movimiento, primeros, ultimos, costo_actual, r_sol,t_sol);

    if(tam_movimiento == -1){
      break;
    }

    hacer_movimiento(actual,movimiento,tam_movimiento, primeros, ultimos);
    
    //Se prohibe el movimiento ejecutado
    taboo[movimiento[0]->id][movimiento[tam_movimiento-1]->id] = taboo_size;

    costo_actual = costo_solucion(primeros, ultimos, r_sol, t_sol);

    if (costo_actual < costo_mejor) {
      costo_mejor = costo_actual;
      
      //Se guarda la mejor solucion
      for(j=0; j<nro_m; j++) {
        operacion *op = primeros[j];
        for (k=0; k<nro_t; k++) {
          mejor_solucion[j][k] = op;
          op = op->sm;
        }
      }
      //Se reinicia el contador de iteraciones
      i = 0;
    }
    //se resta 1 a los movimientos prohibidos en taboo si tienen mas de 0
    for (j=0; j<nro_op; j++) {
      for (k=0; k<nro_op; k++) {
	if (taboo[j][k]) taboo[j][k]--;
      }
    }
    nro_iteraciones++;
  }



  // ESTADISTICAS

  printf("%d ", costo_mejor);
  return;

    

  printf("Costo final: %d\n", costo_mejor);
  printf("Numero de iteraciones: %d\n",nro_iteraciones);
  imprimir_solucion(mejor_solucion, r_sol);
}

void seed () {
    struct timeval t;
    gettimeofday(&t,NULL);
    srand(t.tv_sec * t.tv_usec);
}

int main (int argc, char **argv) {
  int error, option;
  extern char *optarg;
  extern int optopt;
  char *archivo_instancia = NULL;
  int (*vecindad)() = NULL;
  int modalidad = 0;
  int taboo_size = 10;
  
  seed();
  clock_t start, end;
  start = clock();

  while ((option = getopt(argc,argv,":af:n:v:i:")) != -1) {
    switch (option) {
      case 'a':
        modalidad = 1;
        break;
      case 'f':
        archivo_instancia = optarg;
        break;
      case 'n':
        taboo_size = atoi(optarg);
        break;
    case 'v':
        if (optarg[0] == '1' && optarg[1] == 0) {
            vecindad = mejor_movimiento_n1;
        } else if (optarg[0] == '2' && optarg[1] == 0) {
            vecindad = mejor_movimiento_na;
        } else {
            printf("ERROR: la opcion -v debe estar seguida por 1 o 2\n");
            exit(1);
        }
        break;
    case ':':
        printf("ERROR: a la opcion -%c le falta su argumento\n",optopt);
        exit(1);
    case '?':
        printf("ERROR: parametro desconocido %c\n",optopt);
        exit(1);
      
    }
  }
  
  if (!archivo_instancia) {
    printf("Debe especificar un archivo de caso de prueba.\nUse el flag -f <archivo>\n");
    exit(1);
  }
  
  if (!vecindad) {
    printf("Debe especificar la funcion de vecindad a utilizar.\nUse el flag -v <vecindad>\n");
    exit(1);
  }
  
  if (error = leer_instancia(archivo_instancia)) {
    if (error == -1) printf("ERROR: la memoria disponible no es suficiente\n");
  	exit(1);
  }

  tabu_search(vecindad,modalidad,taboo_size);

  end = clock();
  printf("%5.2f seg.\n", end);
  return 0;
}
